﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GraphAlgorithm
{
	/// <summary>
	/// Egy gráfot reprezentál.
	/// </summary>
	public class Graph
	{
		/// <summary>
		/// A gráf színezéséhez használható szín.
		/// </summary>
		internal class Color
		{
			/// <summary>
			/// A szín azonosítója.
			/// </summary>
			private int id;

			/// <summary>
			/// A szín súlya.
			/// </summary>
			private double w;

			/// <summary>
			/// Konstruktok azonosítóból és súlyból.
			/// </summary>
			/// <param name="id">A szín azonosítója.</param>
			/// <param name="w">A szín súlya</param>
			private Color( int id, double w )
			{
				this.id = id;
				this.w = w;
			}

			/// <summary>
			/// A szín azonosítója.
			/// </summary>
			internal int ID
			{
				get { return id; }
			}

			/// <summary>
			/// A szín súlya.
			/// </summary>
			internal double W
			{
				get { return w; }
				set { w = value; }
			}

			/// <summary>
			/// Új szín létrehozása a G gráfhoz.
			/// A szín azonosítója a gráfban található eddigi színek alapján jön létre.
			/// Az új szín automatikusan bekerül a gráfban használt színek közé.
			/// A súlya 1.0 lesz.
			/// </summary>
			/// <param name="G">A gráf, amelyhez a létrehozandó szín tartozik.</param>
			/// <returns></returns>
			static internal Color CreateColor( Graph G )
			{
				Color c = new Color( G.nextColorID, 1.0 );
				G.nextColorID++;
				G.usedColors.Add( c );
				return c;
			}
		}

		/// <summary>
		/// Következő létrehozandó csomópont azonosítója.
		/// </summary>
		private int nextID;

		/// <summary>
		/// Következő létrehozandó szín azonosítója.
		/// </summary>
		private int nextColorID;

		/// <summary>
		/// A gráf csomópontjainak listája.
		/// </summary>
		private List<Vertex> vertexes = new List<Vertex>();

		/// <summary>
		/// A gráfban használt színek listája.
		/// </summary>
		private List<Color> usedColors = new List<Color>();

		/// <summary>
		/// Új gráf létrehozása.
		/// Az új gráf csomópontok és felhasználható színek nélkül jön létre.
		/// </summary>
		public Graph()
		{
			nextID = 0;
			nextColorID = 0;
		}

		/// <summary>
		/// Egy csomópont hozzáadása a gráfhoz.
		/// A csomópont súlya 1 lesz.
		/// </summary>
		public void AddVertex()
		{
			AddVertex( 1 );
		}

		/// <summary>
		/// Csomópontok hozzáadása a gráfhoz.
		/// A csomópontok súlya 1 lesz.
		/// </summary>
		/// <param name="nbr">A csomópontok száma.</param>
		public void AddVertex( int nbr )
		{
			AddVertex( nbr, 1 );
		}

		/// <summary>
		/// Csomópontok hozzáadása a gráfhoz.
		/// </summary>
		/// <param name="nbr">A csomópontok száma.</param>
		/// <param name="w">A csomópontok súlya.</param>
		public void AddVertex( int nbr, int w )
		{
			for( int i = 0; i < nbr; i++ )
			{
				Vertex v = new Vertex( nextID, w );
				vertexes.Add( v );
				nextID++;
			}
		}

		/// <summary>
		/// Szín hozzáadás a gráfban használható színekhez.
		/// </summary>
		public void AddColor()
		{
			Color.CreateColor( this );
		}

		/// <summary>
		/// Színek hozzáadása a gráfban használható színekhez.
		/// </summary>
		/// <param name="nbr">A színek száma.</param>
		public void AddColor( int nbr )
		{
			for( int i = 0; i < nbr; i++ )
			{
				AddColor();
			}
		}

		/// <summary>
		/// Él hozzáadás a gráfhoz.
		/// </summary>
		/// <param name="b">A kezdő csomópont.</param>
		/// <param name="e">A végpont.</param>
		public void AddEdge( int b, int e )
		{
			vertexes[b].Edges.Add( e );
			vertexes[e].Edges.Add( b );
		}

		/// <summary>
		/// Színek hozzáadása a csomópont színeihez.
		/// </summary>
		/// <param name="v">A csomópont.</param>
		/// <param name="colors">A színek</param>
		public void AddColorsToVertex( int v, List<int> colors )
		{
			foreach( int i in colors )
			{
				AddColorToVertex( v, i );
			}
		}

		/// <summary>
		/// Szín hozzáadása a csomópont színeihez.
		/// </summary>
		/// <param name="v">A csomópont.</param>
		/// <param name="color">A szín.</param>
		public void AddColorToVertex( int v, int color )
		{
			vertexes[v].AddColor( usedColors[color] );
		}

		/// <summary>
		/// A csomópont egyedüli lehetséges színének kiválasztása.
		/// </summary>
		/// <param name="v">A csomópont.</param>
		/// <param name="color">A szín.</param>
		public void AddVertexOnlyPossibleColor( int v, int color )
		{
			vertexes[v].AddOnlyPossibleColor( usedColors[color] );
		}


		/// <summary>
		/// Csomópont kiszínezése.
		/// </summary>
		/// <param name="v">A csomópont.</param>
		/// <param name="color">Az új szín.</param>
		public void SetVertexColor( int v, int color )
		{
			vertexes[v].Color = color;
		}

		/// <summary>
		/// Egy csomópont véletlen kiszínezése.
		/// </summary>
		/// <param name="n">A csomópont</param>
		public void RandomizeVertexColor( int n )
		{
			Vertex v = vertexes[n];
			double[] t = new double[v.AvailableColors.Count];
			for( int i = 0; i < v.AvailableColors.Count; i++ )
			{
				t[i] = v.GetAvailableColor( i ).W;
			}

			int index = RandomHelper.RandomIndex( t );
			v.Color = v.GetAvailableColor( index ).ID;
		}

		/// <summary>
		/// Minden csomópontot véletlenszerűen színez ki.
		/// </summary>
		public void RandomizeAllVertexColor()
		{
			for( int i = 0; i < vertexes.Count; i++ )
			{
				RandomizeVertexColor( i );
			}
		}

		/// <summary>
		/// Megkeresi az első olyan élt, amelynek mindkét végpontja azonos színű.
		/// </summary>
		/// <returns>Az első él, amelynek a végpontjai rosszul vannak kiszínezve. Ha nincs ilyen, akkor null.</returns>
		public Edge GetFirstConflict()
		{
			foreach( Vertex v in vertexes )
			{
				int i = v.Color;
				foreach( int e in v.Edges )
				{
					int j = vertexes[e].Color;
					if( i == j )
					{
						return new Edge( v.ID, e );
					}
				}
			}

			return null;
		}

		/// <summary>
		/// Kiegyenlíti színsúlyokat.
		/// </summary>
		public void EqualizeColorWeight()
		{
			int[] colorUses = new int[nextColorID];
			for( int i = 0; i < nextColorID; i++ )
			{
				colorUses[i] = 0;
			}

			foreach( Vertex v in vertexes )
			{
				foreach( int cID in v.AvailableColors )
				{
					colorUses[cID] += v.W;
				}
			}

			int sumUses = 0;
			for( int i = 0; i < nextColorID; i++ )
			{
				sumUses += colorUses[i];
			}

			foreach( Color c in usedColors )
			{
				double w = (double)( sumUses );
				w /= (double)( colorUses[c.ID] );
				c.W = w;
			}
		}

		/// <summary>
		/// Visszaadja egy csomópont színét.
		/// </summary>
		/// <param name="v">A csomópont.</param>
		/// <returns>Visszadja egy csomópont színét.</returns>
		public int GetVertexColor( int v )
		{
			return vertexes[v].Color;
		}

		/// <summary>
		/// Visszaadja, hogy a csomópontot hányféle színre lehet színezni.
		/// </summary>
		/// <param name="v">A csomópont.</param>
		/// <returns>Visszaadja, hogy a csomópontot hányféle színre lehet színezni.</returns>
		public int GetVertexColorCount( int v )
		{
			return vertexes[v].AvailableColors.Count;
		}

		/// <summary>
		/// Igaz, ha van olyan csomópont, akihez nem állítottunk be lehetséges színt.
		/// </summary>
		/// <returns>Igaz, ha van olyan csomópont, akihez nem állítottunk be lehetséges színt.</returns>
		public bool HaveVertexWithOutColor()
		{
			foreach( Vertex v in vertexes )
			{
				if( v.AvailableColors.Count == 0 ) return true;
			}

			return false;
		}

		/// <summary>
		/// A gráf csomópontjainak száma.
		/// </summary>
		public int VertexCount
		{
			get
			{
				return vertexes.Count;
			}
		}

		/// <summary>
		/// Igaz, ha az i. és j. csomópont között van él.
		/// </summary>
		/// <param name="i">Az i. csomópont.</param>
		/// <param name="j">A j. csomópont.</param>
		/// <returns>Igaz, ha az i. és j. csomópont között van él.</returns>
		public bool HaveEdge( int i, int j )
		{
			if( vertexes[i].Edges.Contains( j ) ) return true;
			else return false;
		}

		/// <summary>
		/// Igaz ha az i. és j. csomópont színlistájának van közös eleme.
		/// </summary>
		/// <param name="i">Az i. csomópont.</param>
		/// <param name="j">A j. csomópont.</param>
		/// <returns>Igaz ha az i. és j. csomópont színlistájának van közös eleme.</returns>
		public bool HaveCommonColor( int i, int j )
		{
			if( vertexes[i].AvailableColors.Intersect( vertexes[j].AvailableColors ).Any() )
			{
				return true;
			}
			else
			{
				return false;
			}
		}

		/// <summary>
		/// Az i. pont fokszáma.
		/// </summary>
		/// <param name="i">Az i. pont.</param>
		/// <returns>Az i. pont fokszáma.</returns>
		public int Degree( int i )
		{
			return vertexes[i].Edges.Count;
		}

		/// <summary>
		/// Az i. és j. pont színlistájának metszetének mérete.
		/// </summary>
		/// <param name="i">Az i. pont.</param>
		/// <param name="j">A j. pont.</param>
		/// <returns>Az i. és j. pont színlistájának metszetének mérete.</returns>
		public int IntersectSize( int i, int j )
		{
			return vertexes[i].AvailableColors.Intersect( vertexes[j].AvailableColors ).ToList().Count;
		}

		/// <summary>
		/// Kiírja a gráf adatait.
		/// </summary>
		public void Print()
		{
			Console.WriteLine( "==========================" );
			foreach( Vertex v in vertexes )
			{
				v.Print();
				Console.WriteLine( "---------------------------" );
			}
			Console.WriteLine( "==========================" );
		}

	}
}
